// easy

// 给一个二叉树，计算它的直径长度
// 直径长度：任意两个节点路径长度中的最大值

// 解题思路
// 直径长度的理解，不是简单的左子树高度+右子树高度，而是当前节点的直径 = max(左子树高度 + 右子树高度， 所有子树中最大直径)
// 在递归求解子树高度的时候维护一个maxDiameter参数，每次递归都要去判断当前 （左子树高度 + 右子树高度） 是否大于 maxDiameter，然后更新最大值

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
        },
    },
    right: {
        val: 6,
    },
};

function diameterOfBinaryTree(root) {
    // 保存当前最大直径
    let maxDiameter = 0
    function height(root) {
        if (!root) {
            return 0
        }
        let leftHeight = height(root.left)
        let rightHeight = height(root.right)
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight)
        return Math.max(leftHeight, rightHeight) + 1
    }
    height(root)
    return maxDiameter
}

console.log(diameterOfBinaryTree(root))